package com.xupt.easy.link;


import java.util.List;

/**
 * @author zhaoxin
 * @title: IsPalindrome
 * @projectName LeetCode
 * @description: 回文链表
 * @date 2019/11/21 15:00
 */
public class IsPalindrome234 {

    /**
     * 请判断一个链表是否为回文链表。
     *
     * 示例 1:
     *
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     *
     * 输入: 1->2->2->1
     * 输出: true
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        // 空链表和只有一个节点的链表
        if (head == null){
            return true;
        }
        if (head.next == null){
            return true;
        }
        // 创建快慢指针
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;

        // 慢指针每次走一个节点，快指针每次走两个节点。当快指针走到链表尾部，慢指针刚好走到中间部位
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // 快指针指向后半段链表首位
        fast = slow.next;
        // 断开链表
        slow.next = null;
        // 慢指针指向前半段链表
        slow = dummyNode.next;


        // 反转后半段链表
        ListNode prev = null;
        ListNode curr = fast;
        while (curr != null){
            ListNode nodeTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nodeTemp;
        }
        // 两段链表比较
        while (prev != null && slow != null){
            if (prev.val != slow.val){
                return false;
            }
            prev = prev.next;
            slow = slow.next;
        }

        return true;
    }

    public static void main(String[] args) {
        IsPalindrome234 isPalindrome234 = new IsPalindrome234();
        ListNode listNode0 = new ListNode(1);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode0.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        //listNode3.next = listNode4;
        //listNode4.next = listNode5;


        isPalindrome234.isPalindrome(listNode0);


    }

}
